package org.example.myleet.p1044;

import java.util.HashMap;

public class Solution {

    private static final long MOD = 1000000007L;

    private String result;

    public String longestDupSubstring(String s) {
        result = "";
        int l = 1, r = s.length();
        char[] sArr = s.toCharArray();
        int[] encoded = new int[sArr.length];
        for (int i = 0; i < sArr.length; ++i) {
            encoded[i] = sArr[i] - 'a';
        }
        while (r > l) {
            int m = (r + l) >> 1;
            if (hasDupSubStringForLen(m, encoded)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        ++l;
        while (l < s.length() && hasDupSubStringForLen(l, encoded)) {
            ++l;
        }
        return result;
    }

    public boolean hasDupSubStringForLen(int len, int[] s) {
        HashMap<Long, Integer> map = new HashMap<>();
        Integer p;
        int i = 0;
        long hash = 0L, suffix = 1L;
        for (; i < len; ++i) {
            hash = (hash + s[i]) * 31;
            hash %= MOD;
            suffix *= 31;
            suffix %= MOD;
        }
        map.put(hash, i - 1);
        for (; i < s.length; ++i) {
            long head = suffix * s[i - len];
            while (hash < head) {
                hash += MOD;
            }
            hash -= suffix * s[i - len];
            hash = (hash + s[i]) * 31;
            hash %= MOD;
            if (null != (p = map.get(hash))) {
                if (isIdentical(s, p, i, len)) {
                    char[] r = new char[len];
                    for (int j = 0; j < len; ++j) {
                        r[j] = (char) (s[i - len + 1 + j] + 'a');
                    }
                    result = new String(r);
                    return true;
                }
            } else {
                map.put(hash, i);
            }
        }
        return false;
    }

    private boolean isIdentical(int[] s, int i, int j, int len) {
        while (len > 0) {
            if (s[i] != s[j]) {
                return false;
            }
            --i;
            --j;
            --len;
        }
        return true;
    }
}
